第七章复习题 20200106

题出错了

3

实现任意二叉树，m 个树叶，n 个结点，深度为 h，则（）。

（0.8 分）

• A、
  [h+m=2n](javascript:void(0);)
• B、
  [n=h+m](javascript:void(0);)
• C、
  [n=2h-1](javascript:void(0);)
• D、
  [m=h-1](javascript:void(0);)
  我排除了 ABCD 都不对，我举得飞旋就选 C

23

以下说法错误的是 ()（0.8 分）

0.0分

• A、
  [二叉树与树具有相同的树形结构](javascript:void(0);)
• B、
  [二叉树可以是空集](javascript:void(0);)
• C、
  [二叉树中任一结点的两棵子树有次序之分](javascript:void(0);)
• D、
  [二叉树的任一结点都有两棵子树](javascript:void(0);)
  我的答案：D

正确答案：A

AD 都是错的

33

由二叉树的前序和后序遍历序列（）惟一确定这棵二叉树。（0.8 分）

0.0分

• A、
  [不能](javascript:void(0);)
• B、
  [不确定](javascript:void(0);)
• C、
  [能](javascript:void(0);)
• D、
  [无关联](javascript:void(0);)
  我的答案：B

正确答案：A

严谨的讲，应该是不一定，正确答案是 A 不能

76

下面哪棵不是完全二叉树（）

（0.8 分）

• A、
  
• B、
  
• C、
  
• D、
  

B、D 都不是，答案选 B

82

以下说法正确的是 ()（0.8 分）

• A、
  [在二叉树中插人结点，该二叉树便不再是二叉树](javascript:void(0);)
• B、
  [一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2k-1-1余下的n-2k-1+1个结点在第k层的任一位置上](javascript:void(0);)
• C、
  [若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。](javascript:void(0);)
• D、
  [若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍历序列中的最后一个结点。](javascript:void(0);)

B 是对的，C 是重言式也是对的，且 b 的标号非常不清晰。答案是 B

107

以下说法正确的是 ()

（0.8 分）

• A、
  [若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离历序列中的最后一个结点](javascript:void(0);)
• B、
  [二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点](javascript:void(0);)
• C、
  [在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点](javascript:void(0);)
• D、
  [若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。](javascript:void(0);)
  这题 B 是对的，D 是重言式也是对的，答案是 B

108

森林和二叉树的关系，目的是为了（）（4.8 分）

• A、
  [将树、森林转换成二叉树](javascript:void(0);)
• B、
  [将树、森林按二叉树的存储方式进行存储](javascript:void(0);)
• C、
  [借助二叉树上的运算方法去实现对树的一些运算](javascript:void(0);)
• D、
  [体现一种技巧，没有什么实际意义](javascript:void(0);)
  我选 B，不确定，且这个题题干不全，答案是 C，

完整题干是讨论树、森林和二叉树的关系，目的是为了（）

做题不确定

2

以下说法错误的是 ()（0.8 分）

• A、
  [存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同](javascript:void(0);)
• B、
  [在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树](javascript:void(0);)
• C、
  [二叉树是树转化过来的的特殊情形](javascript:void(0);)
• D、
  [由树转换成二叉树，其根结点的右子树总是空的](javascript:void(0);)
  我选 D，不确定 BC

3

实现任意二叉树，m 个树叶，n 个结点，深度为 h，则（）。

（0.8 分）

• A、
  [h+m=2n](javascript:void(0);)
• B、
  [n=h+m](javascript:void(0);)
• C、
  [n=2h-1](javascript:void(0);)
• D、
  [m=h-1](javascript:void(0);)
  我排除了 ABCD 都不对，我举得飞旋就选 C

5

设某哈夫曼树中有 199 个结点，则该哈夫曼树中有（）个叶子结点。（0.8 分）

• A、
  [101](javascript:void(0);)
• B、
  [102](javascript:void(0);)
• C、
  [99](javascript:void(0);)
• D、
  [100](javascript:void(0);)
  我觉得叶子比分支多一个，不会证明，选了 D，只有度为 0 和度为 2 的结点，n0-n2=1 所以！证出来了

6

设深度为 k 的二叉树上只有度为 0 和度为 2 的节点，则这类二叉树上所含结点总数最少（）个（0.8 分）

• A、
  [2k](javascript:void(0);)
• B、
  [k+1](javascript:void(0);)
• C、
  [2k-1](javascript:void(0);)
• D、
  [2k+1](javascript:void(0);)

肯定是 2k-1，每一层有 2 个，第一层有 1 个，做到 17 题才会

12

已知某二叉树的后序遍历序列是 dabec,中序遍历序列是 deabc,它的前序遍历序列是（）

（0.8 分）

• A、
  [acbed](javascript:void(0);)
• B、
  [cedba](javascript:void(0);)
• C、
  [decab](javascript:void(0);)
• D、
  [deabc](javascript:void(0);)
  我选 B，不够熟练

20

如果 T2 是由有序树 T 转化而来的二叉树，那么 T 中结点的前序就是 T2 中结点的（）

（0.8 分）

• A、
  [层次序](javascript:void(0);)
• B、
  [前序](javascript:void(0);)
• C、
  [后序](javascript:void(0);)
• D、
  [中序](javascript:void(0);)
  我选 B，不够确定，还要查书

33

由二叉树的前序和后序遍历序列（）惟一确定这棵二叉树。（0.8 分）

• A、
  [不能](javascript:void(0);)
• B、
  [不确定](javascript:void(0);)
• C、
  [能](javascript:void(0);)
• D、
  [无关联](javascript:void(0);)
  我选 B，确实是 B 不确定，可我估计答案是 A 不能

35

二叉树是非线性数据结构，()。（0.8 分）

• A、
  [它不能用顺序存储结构存储;](javascript:void(0);)
• B、
  [不是所有的二叉树树形结构都适用顺序存储结构](javascript:void(0);)
• C、
  [它不能用链式存储结构存储;](javascript:void(0);)
• D、
  [顺序存储结构和链式存储结构都不能使用](javascript:void(0);)
  我选 B，但我觉得顺序存储的优缺点是一定的，和二叉树是哪个，具体长成什么样关系不大

36

如下图所示，从结点 B 的兄弟结点有 () 个。


（0.8 分）

• A、
  [5](javascript:void(0);)
• B、
  [2](javascript:void(0);)
• C、
  [3](javascript:void(0);)
• D、
  [4](javascript:void(0);)
  我选 B，可我又觉得也需要算上 B 自己

39

设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序 ()

（0.8 分）

• A、
  [先序和中序相同，而与后序不同](javascript:void(0);)
• B、
  [都不相同](javascript:void(0);)
• C、
  [完全相同](javascript:void(0);)
• D、
  [中序和后序相同，而与先序不同](javascript:void(0);)
  我选 C，但我不确定

40

具有 n(n>0) 个结点的完全二叉树的深度为（）。

（0.8 分）

• A、
  
• B、
  
• C、
  [log₂(n)+1](javascript:void(0);)
• D、
  [élog₂(n)+1](javascript:void(0);)
  我选 C，但我认为是 log2（n+1）上取整，后来想了想好像一样

43

在一棵具有 k 层的满三叉树中，结点总数为 ()。

（0.8 分）

• A、
  
• B、
  
• C、
  
• D、
  

我选 D，等比数列求和

44

如下图所示，从根结点到结点 G 的路径长度为 ()。


（0.8 分）

• A、
  [4](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [2](javascript:void(0);)
• D、
  [3](javascript:void(0);)
  我选 C，应该是 2 吧，不能是 3 吧

45

以下说法错误的是 ()（0.8 分）

• A、
  [哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。](javascript:void(0);)
• B、
  [已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。](javascript:void(0);)
• C、
  [在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。](javascript:void(0);)
• D、
  [若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。](javascript:void(0);)
  我选的 B，但我觉得全都是对的。

48

以下说法错误的是 ()（0.8 分）

• A、
  [在二叉链表上，求根，求左、右孩子等很容易实现](javascript:void(0);)
• B、
  [在二叉链表上，求双亲运算的时间性能很好](javascript:void(0);)
• C、
  [在三叉链表上，二叉树的求双亲运算很容易实现](javascript:void(0);)
• D、
  [完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达](javascript:void(0);)
  我选的 B，但我感觉 C 也不对

51

以下说法错误的是 ()（0.8 分）

• A、
  [若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点](javascript:void(0);)
• B、
  [一般在哈夫曼树中，权值越大的叶子离根结点越近](javascript:void(0);)
• C、
  [哈夫曼树中没有度数为1的分支结点](javascript:void(0);)
• D、
  [若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树](javascript:void(0);)
  我选的 D，排除 BC，我不会 A，D，哈夫曼树和森林有什么关系？

56

设 a，b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前的条件是 ()。（0.8 分）

• A、
  [a在b左方](javascript:void(0);)
• B、
  [a是b的子孙](javascript:void(0);)
• C、
  [a在b右方](javascript:void(0);)
• D、
  [a是b的祖先](javascript:void(0);)
  我选 A，不确定

67

用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组 R[1..n] 中，若结点 R[i] 有左孩子，则其左孩子是（）。（0.8 分）

• A、
  [R[2/i]](javascript:void(0);)
• B、
  [R[2i-1]](javascript:void(0);)
• C、
  [R[2i+1]](javascript:void(0);)
• D、
  [R[2i]](javascript:void(0);)
  我选 D，这数组下标挺奇怪的

68

设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

（0.8 分）

• A、
  [高度等于其结点数](javascript:void(0);)
• B、
  [任一结点无左孩子](javascript:void(0);)
• C、
  [空或只有一个结点](javascript:void(0);)
• D、
  [任一结点无右孩子](javascript:void(0);)
  我选 A，很巧妙的问题

69

表达式 A*(B+C)/(D-E+F) 的后缀表达式是（）。

（0.8 分）

• A、
  [ABCDED*+/-+](javascript:void(0);)
• B、
  [A*B+C/D-E+F](javascript:void(0);)
• C、
  [AB*C+D/E-F+](javascript:void(0);)
• D、
  [ABC+*DE-F+/](javascript:void(0);)
  我选 D，有点难，不熟练，我一开始把* 当作根节点了

70

设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。（0.8 分）

• A、
  [4m](javascript:void(0);)
• B、
  [2m](javascript:void(0);)
• C、
  [2m+1](javascript:void(0);)
• D、
  [2m-1](javascript:void(0);)
  我选 B，真的好难，2*（2m-1）-（2m-1-1）

所有 不空的

80

一棵二叉树有 n 个结点，要按某顺序对该二叉树中的结点编号，（号码为 1-n），编号须具有如下性质：二叉树中任一结点 V，其编号等于其左子树中结点的最大编号加 1。而其右子树中结点的最小编号等于 V 的编号加 1。试问应按（）遍历顺序编号。

（0.8 分）

• A、
  [前序](javascript:void(0);)
• B、
  [中序](javascript:void(0);)
• C、
  [后序](javascript:void(0);)
• D、
  [层次](javascript:void(0);)
  我选 B，应该是中序，一位内左面都比根小，右面都比根大

81

设 F 是由


、


和


三棵树组成的森林，与 F 对应的二叉树为 B，


、


和


的结点数分别为

、

和

，则二叉树 B 的根结点的左子树的结点数为（）。

（0.8 分）

• A、
  
• B、
  
• C、
  
• D、
  

我选 C，不熟练，查了才会

94

以下说法错误的是 ()（0.8 分）

• A、
  [在三叉链表上，二叉树的求双亲运算很容易实现](javascript:void(0);)
• B、
  [在二叉链表上，求兄弟结点的运算的时间性能很好](javascript:void(0);)
• C、
  [在二叉链表上，求根，求右孩子等很容易实现](javascript:void(0);)
• D、
  [完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达](javascript:void(0);)
  我选 C，感觉求根节点实际上是已知的

104

欲实现任意二叉树的后序遍历的非递归算法二不必使用栈结构，最佳方案是二叉树采用 () 存储结构。

（0.8 分）

• A、
  [三叉链表](javascript:void(0);)
• B、
  [广义表存储结构](javascript:void(0);)
• C、
  [顺序存储结构](javascript:void(0);)
• D、
  [二叉链表](javascript:void(0);)
  我选 A，不确定

108

森林和二叉树的关系，目的是为了（）（4.8 分）

• A、
  [将树、森林转换成二叉树](javascript:void(0);)
• B、
  [将树、森林按二叉树的存储方式进行存储](javascript:void(0);)
• C、
  [借助二叉树上的运算方法去实现对树的一些运算](javascript:void(0);)
• D、
  [体现一种技巧，没有什么实际意义](javascript:void(0);)
  我选 B，不确定，且这个题题干不全

113

根据二叉树的定义可知二叉树共有（）种不同的形态。

（0.8 分）

• A、
  [6](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [4](javascript:void(0);)
  我选 D，实际上我不会，我感觉题错了

116

设 a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前面的条件是（）。

（0.8 分）

• A、
  [a在b的左方](javascript:void(0);)
• B、
  [a是b的子孙](javascript:void(0);)
• C、
  [a是b的祖先](javascript:void(0);)
• D、
  [a在b的右方](javascript:void(0);)
  我选 A，实际上我不太会

117

用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组 R[1..N] 中，若结点 R[i] 有右孩子，则其右孩子是（）。

（0.8 分）

• A、
  [R[2i+1]](javascript:void(0);)
• B、
  [R[2/i]](javascript:void(0);)
• C、
  [R[2i-1]](javascript:void(0);)
• D、
  [R[2i]](javascript:void(0);)
  我选 A，他这个下标有点奇怪，我不太确定

我的错题

2

以下说法错误的是 ()（0.8 分）

0.0分

• A、
  [存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同](javascript:void(0);)
• B、
  [在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树](javascript:void(0);)
• C、
  [二叉树是树转化过来的的特殊情形](javascript:void(0);)
• D、
  [由树转换成二叉树，其根结点的右子树总是空的](javascript:void(0);)
  我的答案：D

应该选 C

15

在一棵二叉树上第 5 层的结点数最多为（）个。

（0.8 分）

0.0分

• A、
  [8](javascript:void(0);)
• B、
  [32](javascript:void(0);)
• C、
  [15](javascript:void(0);)
• D、
  [16](javascript:void(0);)
  我的答案：B

应该选 D

23

以下说法错误的是 ()（0.8 分）

0.0分

• A、
  [二叉树与树具有相同的树形结构](javascript:void(0);)
• B、
  [二叉树可以是空集](javascript:void(0);)
• C、
  [二叉树中任一结点的两棵子树有次序之分](javascript:void(0);)
• D、
  [二叉树的任一结点都有两棵子树](javascript:void(0);)
  我的答案：D

错题，没选错

33

由二叉树的前序和后序遍历序列（）惟一确定这棵二叉树。（0.8 分）

0.0分

• A、
  [不能](javascript:void(0);)
• B、
  [不确定](javascript:void(0);)
• C、
  [能](javascript:void(0);)
• D、
  [无关联](javascript:void(0);)
  我的答案：B

应该选 A

37

设一棵完全二叉树中有 65 个结点，则该完全二叉树的深度为（）。（0.8 分）

0.0分

• A、
  [8](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [6](javascript:void(0);)
  我的答案：D

应该选 C

50

假定一棵三叉树的结点数为 50，则它的最小高度为 ()。

（0.8 分）

0.0分

• A、
  [6](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [3](javascript:void(0);)
• D、
  [4](javascript:void(0);)
  我的答案：D

应该选 B

53

19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为 ()。（0.8 分）

0.0分

• A、
  [6](javascript:void(0);)
• B、
  [8](javascript:void(0);)
• C、
  [5](javascript:void(0);)
• D、
  [7](javascript:void(0);)
  我的答案：C

应该选 A

65

设某棵二叉树的高度为 10，则该二叉树上叶子结点最多有（）。

（0.8 分）

0.0分

• A、
  [20](javascript:void(0);)
• B、
  [1024](javascript:void(0);)
• C、
  [512](javascript:void(0);)
• D、
  [256](javascript:void(0);)
  我的答案：B

应该选 C

76

下面哪棵不是完全二叉树（）

（0.8 分）

0.0分

• A、
  
• B、
  
• C、
  
• D、
  

我的答案：D

94

以下说法错误的是 ()（0.8 分）

0.0分

• A、
  [在三叉链表上，二叉树的求双亲运算很容易实现](javascript:void(0);)
• B、
  [在二叉链表上，求兄弟结点的运算的时间性能很好](javascript:void(0);)
• C、
  [在二叉链表上，求根，求右孩子等很容易实现](javascript:void(0);)
• D、
  [完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达](javascript:void(0);)
  我的答案：C

应该选 B

99

深度为 5 的二叉树最少有 () 个结点。（0.8 分）

0.0分

• A、
  [32](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [10](javascript:void(0);)
• D、
  [31](javascript:void(0);)
  我的答案：A

应该选 B，没说是完全二叉树

107

以下说法正确的是 ()

（0.8 分）

0.0分

• A、
  [若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离历序列中的最后一个结点](javascript:void(0);)
• B、
  [二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点](javascript:void(0);)
• C、
  [在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点](javascript:void(0);)
• D、
  [若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。](javascript:void(0);)
  我的答案：A

应该选 B

108

森林和二叉树的关系，目的是为了（）（4.8 分）

0.0分

• A、
  [将树、森林转换成二叉树](javascript:void(0);)
• B、
  [将树、森林按二叉树的存储方式进行存储](javascript:void(0);)
• C、
  [借助二叉树上的运算方法去实现对树的一些运算](javascript:void(0);)
• D、
  [体现一种技巧，没有什么实际意义](javascript:void(0);)
  我的答案：B

应该选 C

113

根据二叉树的定义可知二叉树共有（）种不同的形态。

（0.8 分）

0.0分

• A、
  [6](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [4](javascript:void(0);)
  我的答案：D

应该选 B